iT邦幫忙

2025 iThome 鐵人賽

DAY 24
0
自我挑戰組

從零開始學習LeetCode系列 第 24

Day 24 Remove Duplicates from Sorted Array II

  • 分享至 

  • xImage
  •  

題目:給你一個 排序好的整數陣列 nums,請你「原地」移除重複,使每個元素 最多出現兩次,
並返回移除後的陣列長度
https://ithelp.ithome.com.tw/upload/images/20251007/20169339aWFKSi7ky0.jpg


解法一
https://ithelp.ithome.com.tw/upload/images/20251007/20169339PkMkK21xx5.jpg

  • 思路簡單但太慢
  • 適合初學理解結構

註解

  • 從第三個數(索引 2)開始檢查
  • 若連續三個數一樣,就刪掉當前的 nums[i]
  • 否則繼續往下
  • 缺點:pop() 操作仍舊是 O(n²) 時間複雜度

理解

  • 這就像整理書架時:「同一本書最多留兩本」,
    多的就拿掉,重排一次又一次

解法二
https://ithelp.ithome.com.tw/upload/images/20251007/20169339CLcFukl6ce.jpg

  • 雙指針法
  • 一次遍歷 O(n)
  • 原地修改、順序保留

註解

  • 由於最多允許 2 次,前兩個元素必保留
  • 從第三個數開始檢查(fast = 2)
  • 比較 nums[fast] 與 nums[slow - 2]
  • 若不同 → 表示不超過兩次,可保留
  • 若相同 → 已達上限,跳過
  • 最終返回長度 slow

理解

  • 可以想像書架上每本書最多只能放兩本。
    你拿著一個「檢查尺(fast)」一路掃,如果遇到和兩本前面那本不同的,就能放進來

解法三
https://ithelp.ithome.com.tw/upload/images/20251007/20169339Lbt2JCZHE5.jpg

  • 計數法
  • 可彈性調整允許次數
  • 思路清晰但稍長

註解

  • count 紀錄當前數字出現次數
  • 若次數 ≤ 2 就保留
  • 超過 2 次就跳過不存入

差異

  • 這版邏輯更直覺,但比起第二種略微冗長
  • 好處是可改成「允許 N 次」的版本(更彈性)

上一篇
Day 23 Remove Duplicates from Sorted Array
系列文
從零開始學習LeetCode24
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言